import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/3 10:15
 * @description 动态规划
 */
public class Solution2 {
    public static void main(String[] args) {

    }
    public boolean stoneGame(int[] piles) {
        int length = piles.length;
        // dp[i][j] 当剩下石头堆为 下标 i 到 j时，玩家之间石头数量之差
        int[][] dp = new int[length][length];
        for (int i = 0; i < length; i++) {
            // 玩家只能取第i堆石头，那么差为 piles[i]
            dp[i][i] = piles[i];
        }
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                // 先手从左端点取石头，那么差值为 piles[i] - (后手）dp[i + 1][j]。
                // 先手从右端点取石头，那么后手从 dp[i][j-1]取最优，那么石头差值 为 piles[j] - dp[i][j-1]
                dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }
        return dp[0][length - 1] > 0;
    }

}
